--[[
    A*算法
    F = G + H
    G：从起点走到当前格子的成本，也就是已经花费了多少步。
    H：在不考虑障碍的情况下，从当前格子走到目标格子的距离，也就是
        离目标还有多远。
    F：G和H的综合评估，也就是从起点到达当前格子，再从当前格子到达
        目标格子的总步数。

    openList: 开放列表放没使用过的节点
    closeList: 已使用过的节点

    1. 从openList里取一个f值最小的节点作为当前节点, 把当前节点放入closeList
    2. 查看当前节点的相邻节点，放入openList
    3. 如果放入openList的节点等于目标节点，说明找到了
    4. closeList节点能过 parent 回溯路径

    local node = {
        id --标记
        x
        y
        G
        H
        F
        parent --指向父节点
    }
--]]

local table_remove = table.remove
local table_insert = table.insert

require("dump")

local AStar = {}

function AStar.new(...)
    local instance = setmetatable({}, {__index=AStar})
    instance:ctor(...)
    return instance
end

function AStar:ctor()
    self.map = {
        {0,0,0,0,0,0,0,0,0,0},--1
        {0,0,0,0,0,0,0,0,0,0},--2
        {0,0,0,0,1,0,0,0,0,0},--3
        {0,2,0,0,1,0,0,3,0,0},--4
        {0,0,0,0,1,0,0,0,0,0},--5
        {0,0,0,0,0,0,0,0,0,0},--6
        {0,0,0,0,0,0,0,0,0,0},--7

    }
    self.id = 0
    self.openList = {}
    self.closeList = {}
    self.cur_node = nil
end

function AStar:addOpenNode(node)
    table_insert(self.openList, node)
end

function AStar:addCloseLis(node)
    table_insert(self.closeList, node)
end

--找到最小F节点
function AStar:findMin()
    local min = nil
    local index = nil
    for k, v in pairs(self.openList) do
        if not min then
            min = v
            index = k
        else
            if min.F > v.F then
                min = v
                index = k
            end
        end
    end
    if index then
        table_remove(self.openList, index)
        table_insert(self.closeList, min)
    end
    return min
end

--找到附近节点
function AStar:findNeighbors()
    if not self.cur_node then
        return
    end
    local x = self.cur_node.x
    local y = self.cur_node.y
    if self:isValidNode(x+1, y) then
        local node = self:creatNode(x+1, y)
        self:addOpenNode(node)
    end
    if self:isValidNode(x-1, y) then
        local node = self:creatNode(x-1, y)
        self:addOpenNode(node)
    end
    if self:isValidNode(x, y+1) then
        local node = self:creatNode(x, y+1)
        self:addOpenNode(node)
    end
    if self:isValidNode(x, y-1) then
        local node = self:creatNode(x, y-1)
        self:addOpenNode(node)
    end
end

function AStar:isValidNode(x, y)
    if self.map[y][x] and self.map[y][x] ~= 0 then
        if self.map[y][x] == 3 then
            return true
        end
        return false
    end
    for k, v in pairs(self.openList) do
        if v.x == x and v.y == y then
            return false
        end
    end
    for k, v in pairs(self.closeList) do
        if v.x == x and v.y == y then
            return false
        end
    end

    return true
end

function AStar:creatNode(x, y)
    self.id = self.id + 1
    local F = 0
    local G = 0
    local H = 0
    if self.cur_node then
        G = self.cur_node.G + 1
    end
    if self.end_node then
        H = math.abs(self.end_node.x - x ) + math.abs(self.end_node.y - y)
    end
    F = G + H
    return {
        id = self.id,
        x = x,
        y = y,
        F = F,
        G = G,
        H = H,
        parent = self.cur_node,
    }
end

function AStar:start()

    for y, v in pairs(self.map) do
        for x, n in pairs(v) do
            if n == 2 then --2代表开始节点
                self.start_node = self:creatNode(x, y)
            end
            if n == 3 then --3代表目标结点
                self.end_node = self:creatNode(x, y)
            end
        end
    end
    self:addOpenNode(self.start_node)
    print("self.start_node:", tostring(self.start_node))
    print("self.end_node:", tostring(self.end_node))

    while(true) do
        if #self.openList > 0 then
            if self:isTarget() then
                break
            end
            self.cur_node = self:findMin()
            self:findNeighbors()
            --print("___", self.cur_node)
        else
            break
        end
    end
    local node = self.cur_node
    print("path: end->start")
    while node  do
        print(node.id, node.y, node.x)
        node = node.parent
    end
end

function AStar:isTarget()
    if self.cur_node and self.cur_node.x == self.end_node.x and self.cur_node.y == self.end_node.y then
        return true
    else
        return false
    end
end
------------------------------------------------------------------
--测试
------------------------------------------------------------------

if arg and arg[0] == "astar.lua" then
    local time_start = os.time()
    local a = AStar.new()
    a:start()


    print("time:", os.time()-time_start)
end

return AStar